package com.platform.modules.alg.alglib.hdu4010;

public class Hdu4010 {
    private int inf = 0x3f3f3f3f;
    private int N = 300005;

    int n, m, top;
    int c[][] = new int[N][2];
    int fa[] = new int[N];
    int v[] = new int[N];
    int st[] = new int[N];
    int add[] = new int[N];
    int mx[] = new int[N];
    int rev[] = new int[N];

    void update(int x) {
        int l = c[x][0], r = c[x][1];
        mx[x] = Math.max(mx[l], mx[r]);
        mx[x] = Math.max(mx[x], v[x]);
    }

    void pushdown(int x) {
        int l = c[x][0], r = c[x][1];
        if (rev[x] == 1) {
            rev[l] ^= 1;
            rev[r] ^= 1;
            rev[x] ^= 1;
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
        if (add[x] > 0) {
            if (l > 0) {
                add[l] += add[x];
                mx[l] += add[x];
                v[l] += add[x];
            }
            if (r > 0) {
                add[r] += add[x];
                mx[r] += add[x];
                v[r] += add[x];
            }
            add[x] = 0;
        }
    }

    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }

    void rotate(int x) {
        int y = fa[x], z = fa[y], k;
        if (c[y][0] == x) {
            k = 1;
        } else {
            k = 0;
        }
        if (!isroot(y)) c[z][c[z][1] == y ? 1 : 0] = x;
        fa[x] = z;
        fa[y] = x;
        fa[c[x][k]] = y;
        c[y][k == 0 ? 1 : 0] = c[x][k];
        c[x][k] = y;
        update(y);
        update(x);
    }

    void splay(int x) {
        top = 0;
        st[++top] = x;
        for (int i = x; !isroot(i); i = fa[i])
            st[++top] = fa[i];
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }

    void access(int x) {
        for (int t = 0; x > 0; t = x, x = fa[x]) {
            splay(x);
            c[x][1] = t;
            update(x);
        }
    }

    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }

    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }

    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }

    void cut(int x, int y) {
        split(x, y);
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }

    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }

    void addval(int x, int y, int val) {
        split(x, y);
        add[y] += val;
        mx[y] += val;
        v[y] += val;
    }

    public String output = "";

    public String cal(String input) {
        int opt, x, y, w;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);

        for (int i = 0; i <= n; i++)
            add[i] = rev[i] = fa[i] = c[i][0] = c[i][1] = 0;
        mx[0] = -inf;
        for (int i = 1; i < n; i++) {
            String[] num = line[i].split(" ");
            x = Integer.parseInt(num[0]);
            y = Integer.parseInt(num[1]);
            link(x, y);
        }
        String[] wi = line[n].split(" ");
        for (int i = 1; i <= n; i++) {
            v[i] = Integer.parseInt(wi[i - 1]);
            mx[i] = v[i];
        }
        m = Integer.parseInt(line[n + 1]);
        int count = 0;
        while (m-- > 0) {
            String[] query = line[n + 2 + count++].split(" ");
            opt = Integer.parseInt(query[0]);
            x = Integer.parseInt(query[1]);
            y = Integer.parseInt(query[2]);
            switch (opt) {
                case 1:
                    if (findroot(x) == findroot(y)) {
                        output += "-1\n";
                        break;
                    }
                    link(x, y);
                    break;
                case 2:
                    if (findroot(x) != findroot(y) || x == y) {
                        output += "-1\n";
                        break;
                    }
                    cut(x, y);
                    break;
                case 3:
                    w = x;
                    x = y;
                    y = Integer.parseInt(query[3]);
                    if (findroot(x) != findroot(y)) {
                        output += "-1\n";
                        break;
                    }
                    addval(x, y, w);
                    break;
                case 4:
                    if (findroot(x) != findroot(y)) {
                        output += "-1\n";
                        break;
                    }
                    split(x, y);
                    output += mx[y] + "\n";
                    break;
            }
        }
        return output;
    }
}
